import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution139 {

    public static class Trie{
        Trie[] tries=new Trie[26];
        boolean end;

        void insert(String word){
            Trie node=this;
            for (char c : word.toCharArray()) {
                if (node.tries[c-'a']==null){
                    node.tries[c-'a']=new Trie();
                }
                node=node.tries[c-'a'];
            }
            node.end=true;
        }

        List<Integer> query(String word){
            Trie node=this;
            List<Integer> list=new ArrayList<>();
            for (int i=0;i<word.length();i++){
                char c=word.charAt(i);
                if (node.tries[c-'a']==null){
                    return list;
                }
                node=node.tries[c-'a'];
                if (node.end){
                    list.add(i+1);
                }
            }
            return list;
        }
    }

    public boolean wordBreak(String s, List<String> wordDict) {
        Trie trie=new Trie();
        for (String s1 : wordDict) {
            trie.insert(s1);
        }
        boolean[] f=new boolean[s.length()+1];
        f[0]=true;
        for (int i=0;i<s.length();i++){
            if (f[i]) {
                List<Integer> list=trie.query(s.substring(i));
                for (Integer integer : list) {
                    f[i+integer]=true;
                }
            }
        }
        return f[s.length()];
    }

    public static void main(String[] args) {
        System.out.println(new Solution139().wordBreak("leet", Arrays.asList("leet","code")));
    }
}
